#include <iostream>
using namespace std;
void print_array(int a[],int n){
	for(int i = 0;i < n;i++){
		cout << a[i] << " ";
	}
	cout <<endl;
}
void swap(int& a,int& b){
	int temp = a;
	a = b;
	b = temp;	
}
// 划分函数
int partition(int arr[],int low,int high){
	int pivot = arr[low];
	int l = low;
	int r = high;
	while(l < r){
		while(l < r && arr[r] >= pivot){
			r--;
		}
		while(l < r && arr[l] <= pivot){
			l++;
		}
		if(l < r){
			swap(arr[l],arr[r]);
		}
	}
	swap(arr[low],arr[l]);
	return l;
	
}

// 快速排序
void qsort(int arr[],int low,int high){
	if(low < high){
		int mid = partition(arr,low,high);
		qsort(arr,low,mid-1);
		qsort(arr,mid+1,high);
	}
}
// 快速排序入口
void quick_sort(int arr[],int n){
	qsort(arr,0,n-1);
	print_array(arr,n);
}

int main(){
	int arr[] = {15,5,2,7,12,6,1,4,3,9,8,10};
	print_array(arr,12);
	quick_sort(arr,12);
	return 0;
}
